Systems and methods exist that that can be used to solve the problem of finding shortest paths through public transport time/space networks, by applying a modification of Dijkstra's shortest path algorithm.
Increasing public transport patronage is an urban challenge and critical element of any public transport strategy. Transport providers must be able to cost effectively supply the traveler with transport information that is: fast, reliable, accessible, comprehensive, accurate, timely, journey specific and complete.
Journey planning algorithms in commercially available journey planners fall into two broad categories. The first type uses pre-calculated algorithms to find “reasonable” paths between defined interchange points in an extensive build step and then uses these at run time to look up journeys. The second, more dynamic type, journey planning at run time, uses mathematical shortest path techniques to calculate the “best” path, which may include one or more “cost” factors, including length of travel distance or duration, a journey avoiding certain change locations or transfers, or combinations of these, etc.
Those skilled in the art will understand that currently existing systems have a number of limitations. Among these are that the existing solutions to the journey planning problem involve running an algorithm to find a set of journeys based on input criteria, then applying any post filter conditions on the results. If any of the found journeys fail any post filtering criteria, the only option is to tweak the input parameters to come up with other options. This is a very heuristic process, and it is easy to find examples where the re-query also does not find suitable answers. There is also no guarantee about whether the results are optimal in cost, as defined by some selected cost function. Finally, this can be very computationally expensive. If the initial set of answers is not suitable, all of the work done to produce those answers is lost and the re-query will have to start from scratch.
With current solutions, the only way to optimize for secondary criteria (user preferences) is to code them directly into the planning process. This is complex to implement, and requires the core planning algorithm to have detailed knowledge regarding the wider system in which it is being used, which impedes modularity and reuse. Implementing these secondary criteria can also only be done by maintaining extra labels in the dynamic programming process. Further, some criteria don't obey principles of optimality, which makes them very difficult to utilize in a dynamic programming solution such as the K shortest path selection of the present application and the like, due to the computational power, computational time, required memory or other limiting factors. Such principles, as discussed by way of example in “Optimality and Optimisation”, http://ntrg.cs.tcd.ie/undergrad/4ba2/network/luke/opt4.html, may be used to compute actual best paths in a network with some knowledge about such things as details of topology, traffic and other metrics of the network. A function may be generated that is subsequently optimized. A general statement about optimal routing may be made that if node j is on the optimal path from node i to node k, then the optimal route from j to k also falls along the same route. From the optimality principal it is possible to generate optimal routes between sources and destinations for an entire network, forming a so called sink tree. As used herein criteria that are very difficult or difficult to use for a dynamic programming solution, because, e.g., they do not obey the principal of optimality are meant to include both those that mathematically cannot be so used or as to which the use is economically not feasible.
Shortest path solutions for non-timetabled networks are known. See Santos, J., “K shortest path algorithms”, 2006. Department of Mathematics, University of Coimbra, available on the Internet, and Eppstein, D., “Finding the k shortest paths,” 35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154-165. Chen, Y. L. et al, “Finding the Kth shortest path in a time-schedule network,” Naval Research Logistics, Volume 52 Issue 1, Pages 93-102, discusses finding a single kth shortest path in a time scheduled network using a polynomial time algorithm, which suffers from the same shortcomings as finding the single shortest path in a time/space network, as noted above.
Boeing co-pending patent application, Ser. No. 12/099,327, entitled SIMULTANEOUS VEHICLE ROUTING, VEHICLE SCHEDULING, AND CREW SCHEDULING, filed on Apr. 8, 2008, discloses a method for generating a transportation plan, wherein a set of transportation requests are identified, an initial transportation plan having a set of vehicle routes, vehicle schedules, crew designations are created, and simultaneously modified repeatedly until a plan meeting a specific plan objective is determined.
As discussed in T. Yang, et al., “Branch and Bound Algorithm”, available on the Internet, branch and bound is a general search method, which involves starting by considering a root problem (such as the original problem with a complete feasible solution region), and recursively applying bounding, such as with lower-bounding and upper-bounding procedures applied to the root problem.
Accordingly, there is a need in the art for systems and methods to facilitate automated definition of a journey path from a journey origin to a journey destination whereby quantifiable definitions of what is the “best” journey, factoring in user preferences, may be easily and effectively provided.